Dual_EC_DRBG

Материал из Википедии — свободной энциклопедии
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 28 сентября 2017 года; проверки требуют 46 правок.
Перейти к навигации Перейти к поиску

Dual_EC_DRBG (англ.; от Dual Elliptic Curve Deterministic Random Bit Generator) — ранее считавшийся криптографически стойким генератор псевдослучайных чисел, разработанный Агентством национальной безопасности США, один из четырёх криптографически стойких генераторов, стандартизованных NIST как «Special Publication 800-90» (NIST SP 800-90A) в 2006 году[1] и отозванный в 2014 году[2]. Одна из областей применения - криптографические системы для генерации ключей. Алгоритм основан на использовании эллиптических кривых.

Алгоритм

[править | править код]
схема Dual_EC_DRBG

В стандарте NIST SP 800-90A в описании алгоритма используются 2 функции:[3] [4]

  • φ(a) - функция, преобразующая целое число в бинарную последовательность
  • x(A) - функция, возвращающая x-координату точки A

Ход работы:

1) Задается случайное значение t = randomseed()

2) В цикле производятся операции

  1. Вычисляется значение s = φ ( x ( t * P ) )
  2. Вычисляется значение r = φ ( x ( s * Q ) )
  3. Обрезаются старшие 2 байта r
  4. Вывод оставшихся 30 байт r
  5. t = s

Безопасность

[править | править код]

Безопасность Dual_EC_DRBG основана на сложной проблеме теории чисел — проблема Диффи-Хэлмана. Это являлось заявленной причиной включения в NIST SP 800-90.[3] Однако производители генератора не опубликовали математическое доказательство безопасности генератора, и после публикации проекта NIST было показано, что Dual_EC_DRBG не является безопасным из-за того, что на выходе получается большое количество бит за раунд.[5][6] Если использовать точки эллиптической кривой, заданные в стандарте, то из-за слишком большого количества бит на выходе создаётся возможность бэкдора, что даёт возможность злоумышленнику взломать генератор полным перебором. Эта проблема не была исправлена в окончательно опубликованном стандарте, оставив Dual_EC_DRBG небезопасным.[7]

Во многих других стандартах константы, которые должны быть произвольными, выбираются принципом Nothing up my sleeve number. В Dual_EC_DRBG производители не указали, как задаются константы — точки эллиптической кривой P и Q. Поскольку комитет о стандартизации был осведомлен о возможном бэкдоре, в стандарт был включен способ получения своих констант P и Q.[8][9] Но точная формулировка в стандарте была написана так, что использование P и Q, предоставленных в стандарте, требуется для прохождения проверки FIPS 140-2, поэтому в OpenSSL были реализованы именно эти константы, несмотря на осведомленность о бэкдоре и желании использовать более надежные параметры.[10] New York Times позже написала, что АНБ работала во время процесса стандартизации так, чтобы в конечном итоге стать единственным редактором стандарта.[11]

Спустя некоторое время Дэниел Браун и Кристиан Гьёстин опубликовали доказательство безопасности Dual_EC_DRBG, в котором было показано, что сформированные точки эллиптической кривой будут неотличимы от случайных, если[5] :

  1. на выходе будет меньшее количество бит за раунд
  2. точки P и Q будут независимы
  3. следующие три проблемы будут принадлежать классу NP:
    • проблема Диффи-Хэлмана
    • проблема дискретного логарифмирования
    • проблема усеченной точки

Dual_EC_DRBG является довольно медленным генератором в сравнении с альтернативными генераторами, включенными в тот же стандарт, однако эти альтернативы не имеют доказательства безопасности.[12] Дэниел Браун утверждает, что, благодаря доказательству безопасности, генератор можно использовать, несмотря на скорость его работы, при условии что использованы надежные параметры.[12]

Предполагаемый бэкдор позволяет злоумышленнику определить внутреннее состояние генератора случайных чисел после просмотра выхода одного раунда размером 30 байт. Все будущие выходные данные генератора случайных чисел могут быть легко посчитаны, пока внешний источник энтропии не перезагрузит генератор с новым значением t0[4]. Например, использование данного генератора делает небезопасным SSL / TLS, поскольку установка TLS-соединения включает в себя отправку случайно сгенерированного числа в открытом виде.[7] Бэкдор состоит в том, что при использовании констант P и Q из стандарта АНБ знает такое e, что e * Q = P.[4][13] Таким образом, e является секретным ключом, предположительно, известным АНБ, а предполагаемый бэкдор является клептографическим скрытым бэкдором.[14]

Бэкдор

[править | править код]

Первый вывод 30 байт r0 - это x - координата точки без начальных 16 бит. Для каждой кривой, заданной в стандарте, написаны значения X, нуля и одной или двух точек на этой кривой. Таким образом, требуется полностью перебрать не более 17 бит для восстановления исходной точки A.[4]

Если предположить, что:

  1. Что бы найти точку A, нужно s0 * Q = A
  2. Известен секретный ключ e, который задает соотношение Q * e = P

3.То домножив каждую сторону уравнения

e * A = s0 * e * Q = s0 * P [4]

Исходя из этого, есть возможность посчитать s1 = φ ( x ( e * A) ), а затем и r1, затем и последующие s2,...,sn и r2,...,rn. Для этого нужно лишь полным перебором найти A, умножить полученное A на e, затем умножить полученное значение на Q и вывести значение координаты x полученной точки без первых двух байт.[4]

История и стандартизация

[править | править код]

АНБ впервые представила Dual_EC_DRBG в ANSI X9.82 DRBG в начале 2000-х годов, включая параметры, обеспечивающие бэкдор, и в проекте стандарта ANSI был опубликован Dual_EC_DRBG. Так же он был добавлен в стандарт ISO 18031.[8]

По крайней мере два участника комиссии по стандартам и рекомендациям ANSI X9F1, Дэниель Браун и Скотт Ванстон из Certicom,[8] были осведомлены о точном механизме и обстоятельствах, при которых возможен бэкдор, так как в январе 2005 года они подали заявку на патент [15], в котором было описано, как вставить или предотвратить бэкдор в Dual_EC_DRBG. Позже было подтверждено, что данная "ловушка" идентична бэкдору генератора. В 2014 году Мэтью Грин, криптограф и профессор университета Джона Хопкинса,[16][17] критиковал комитет, за то что не был убран этот заранее известный бэкдор.[18] В патенте были описаны 2 условия существования этого бэкдора:

1) Выбрано Q.

Генератор случайных чисел эллиптической кривой избегает escrow keys, выбирая случайно точку Q. Преднамеренное использование escrow keys может обеспечить резервное копирование. Связь между P и Q используется в качестве escrow key и хранится в защищенной области. Администратор регистрирует выход генератора и восстанавливает случайное число с помощью escrow key.

2) Не сокращен выход генератора

Усечение выхода генератора - это альтернативный способ предотвращения атаки с помощью escrow key. Усечение выхода примерно на половину обеспечит то, что выход значений R, связанных с одним выходом r, не будет поддаваться поиску. Например, для 160-битной группы эллиптических кривых число потенциальных точек R в списке составляет около 280, и поиск будет таким же сложным, как задача дискретного логарифмирования. Недостаток этого метода в том, что эффективность генератора уменьшается вдвое, так как вдвое сокращается его выход

По словам Джона Келси, одного из авторов NIST SP 800-90A, вариант выбора достоверного случайного Q был добавлен в стандарт в ответ на бэкдор[9], но таким образом, что проверку FIPS 140-2 генератор проходил бы только с использованием Q от АНБ.[19] Не было понятно, почему стандарт не указывал принцип выбора точки как Nothing up my sleeve number, или почему стандарт не сокращал выход генератора, который предотвращал бы атаку с помощью escrow key.

По сравнению с предыдущим генератором EC PRG усечение выхода было реализовано в Dual_EC_DRBG, который выводил от 1/2 до 2/3 от результата раунда EC PRG.[20] Такое сокращение выхода, все равно оставляло выход генератора предсказуемым и непригодным в качестве криптографически стойкого генератора псевдослучайных чисел. В стандарте говорится, что реализации должны использовать малый max_outlen, но при этом позволяет использовать его только кратным 8 битам. В приложении C стандарта сказано, что вывод меньшего количества бит, сделает выход менее равномерно распределенным, но доказательство безопасности от Брауна полагается на то, что значение показателя max_outlen значительно меньше.

Комиссия по стандартам и рекомендациям ANSI X9F1, в которой обсуждался бэкдор, также включала в себя сотрудников из RSA Security.[21] В 2004 году, RSA Security внедрила реализацию Dual_EC_DRBG, в которой содержался бэкдор, в RSA BSAFE как результат секретной сделки с АНБ. В 2013 году, после того, как New York Times сообщила, что Dual_EC_DRBG содержала бэкдор, в RSA Security заявили, что не знали о бэкдоре при заключении сделки с АНБ, после чего попросили пользователей переключить генератор. На конференции RSA 2014 года исполнительный председатель RSA Security Art Coviello пояснил, что компания терпела убытки от шифрования и решила перестать им заниматься, и вместо этого стала доверять стандартам и организациям по утверждениям стандартов, таких как NIST.[22]

Предварительный вариант NIST SP 800-90A, включая Dual_EC_DRBG, был опубликован в декабре 2005 года. Окончательный вариант был опубликован в июне 2006 года. Документы, показанные Сноуденом, были интерпретированы как предположение, что в Dual_EC_DRBG реализован бэкдор от АНБ, ссылаясь на стремление АНБ быть единственным редактором стандарта.[23] Раннее использование Dual_EC_DRBG в RSA Security было выдвинуто АНБ как аргумент для включения генератора в NIST SP 800-90A.[24] RSA Security впоследствии сказала, что принятие Dual_EC_DRBG в NIST было причиной для его использования.[25]

Потенциальный бэкдор не публиковался за пределами комиссии по стандартизации. Только после презентации Дана Шумова и Нильса Фергюсона в 2007 году бэкдор стал широко известен. Им было поручено реализовать Dual_EC_DRBG для Майкрософт. Кроме того, Фергюсон обсудил возможный бэкдор в 2005 году на совещании X9.[9] Брюс Шнайер написал в статье Wired 2007 года о том, что недостатки Dual_EC_DRGB настолько очевидны, что никто не станет его использовать.[26]

В OpenSSL реализованы все части NIST SP 800-90A, включая Dual_EC_DRBG, несмотря на его сомнительную репутацию. При этом создатели OpenSSL отметили, что они стремятся сделать OpenSSL полным и поэтому реализуют даже небезопасные алгоритмы. OpenSSL не использовал Dual_EC_DRBG по умолчанию, и в 2013 году было обнаружено, что реализация OpenSSL Dual_EC_DRBG не работает и никто не мог ее использовать.[19]

Брюс Шнайер сообщил в декабре 2007 года, что Майкрософт добавила поддержку Dual_EC_DRBG в Windows Vista, хотя по умолчанию она не включена, и Шнайер предупредил о потенциальном бэкдоре.[27] Windows 10 и более поздние версии будут заменять вызовы Dual_EC_DRBG на вызовы генератора на основе AES.[28]

9 сентября 2013 года, из-за информации полученной от Сноудена, а также из-за доклада New York Times о бэкдоре в Dual_EC_DRBG, NIST объявил, что переиздает SP 800-90A и открывает SP 800-90B/C для общественного обсуждения. Сейчас NIST «настоятельно рекомендует» не использовать Dual_EC_DRBG.[29][30] Публикация бэкдора в принятом стандарте стало для NIST серьезным конфузом.[31]

RSA Security сохранила Dual_EC_DRBG как генератор по умолчанию в BSAFE даже после того, как бэкдор стал широко известен. После широко распространившегося беспокойства по поводу бэкдора была предпринята попытка найти программное обеспечение, которое использовало Dual_EC_DRBG, среди которого выделялся BSAFE. В 2013 году, начальник службы безопасности RSA Сэм Карри предоставил сайту Ars Technica обоснование выбора ошибочного стандарта Dual_EC_DRBG по умолчанию по сравнению с альтернативными генераторами.[32] Техническая часть заявления широко критиковалась криптографами.[33] 20 декабря 2013 года агентство Reuters сообщило, что RSA принял секретный платеж в размере 10 миллионов долларов от АНБ, чтобы установить Dual_EC_DRBG по умолчанию в двух продуктах шифрования.[24][34]

Примечания

[править | править код]
  1. ↑ Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised) (англ.) : journal. — National Institute of Standards and Technology, 2007. — March. Архивировано 26 сентября 2007 года.
  2. ↑ "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations". National Institute of Standards and Technology. 2014-04-21. Архивировано 29 августа 2016. Дата обращения: 8 апреля 2019.
  3. ↑ 1 2 NIST Special Publication 800-90. Дата обращения: 21 декабря 2017. Архивировано 28 ноября 2016 года.
  4. ↑ 1 2 3 4 5 6 Dual_Ec_Drbg backdoor: a proof of concept at Aris' Blog - Computers, ssh and rock'n roll (англ.). blog.0xbadc0de.be. Дата обращения: 21 декабря 2017. Архивировано 3 сентября 2018 года.
  5. ↑ 1 2 Daniel R. L. Brown, Kristian Gjøsteen. A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator (англ.) // Advances in Cryptology - CRYPTO 2007. — Springer, Berlin, Heidelberg, 2007-08-19. — P. 466—481. — ISBN 9783540741428, 9783540741435. — doi:10.1007/978-3-540-74143-5_26. Архивировано 4 марта 2018 года.
  6. ↑ Berry Schoenmakers, Andrey Sidorenko. Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator. — 2006. — № 190. Архивировано 15 декабря 2017 года.
  7. ↑ 1 2 "The Many Flaws of Dual_EC_DRBG". A Few Thoughts on Cryptographic Engineering (англ.). 2013-09-18. Архивировано 20 августа 2016. Дата обращения: 14 декабря 2017.
  8. ↑ 1 2 3 "A few more notes on NSA random number generators". A Few Thoughts on Cryptographic Engineering (англ.). 2013-12-28. Архивировано 24 июня 2018. Дата обращения: 14 декабря 2017.
  9. ↑ 1 2 3 Dual EC in X9.82 and SP 800-90. Дата обращения: 15 декабря 2017. Архивировано 15 декабря 2017 года.
  10. ↑ 'Flaw in Dual EC DRBG (no, not that one)' - MARC. marc.info. Дата обращения: 14 декабря 2017. Архивировано 16 октября 2014 года.
  11. ↑ Ball, James (2013-09-06). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian (англ.). Архивировано 25 апреля 2018. Дата обращения: 14 декабря 2017.
  12. ↑ 1 2 [Cfrg] Dual_EC_DRBG ... [was RE: Requesting removal of CFRG co-chair]. www.ietf.org. Дата обращения: 14 декабря 2017. Архивировано 18 августа 2016 года.
  13. ↑ [http://rump2007.cr.yp.to/15-shumow.pdf On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng]. Дата обращения: 7 января 2013. Архивировано 26 февраля 2014 года.
  14. ↑ Dual_Ec_Drbg backdoor: a proof of concept at Aris' Blog - Computers, ssh and rock'n roll (англ.). blog.0xbadc0de.be. Дата обращения: 14 декабря 2017. Архивировано 3 сентября 2018 года.
  15. ↑ Espacenet -Bibliographic data (англ.). worldwide.espacenet.com. Дата обращения: 14 декабря 2017. Архивировано 16 ноября 2018 года.
  16. ↑ Matthew D. Green. Дата обращения: 21 декабря 2017. Архивировано 3 мая 2018 года.
  17. ↑ Matthew Green (англ.). A Few Thoughts on Cryptographic Engineering. Дата обращения: 21 декабря 2017. Архивировано 29 января 2018 года.
  18. ↑ "Hopefully the last post I'll ever write on Dual EC DRBG". A Few Thoughts on Cryptographic Engineering (англ.). 2015-01-14. Архивировано 24 марта 2018. Дата обращения: 14 декабря 2017.
  19. ↑ 1 2 'Flaw in Dual EC DRBG (no, not that one)' - MARC. marc.info. Дата обращения: 15 декабря 2017. Архивировано 16 октября 2014 года.
  20. ↑ "The Many Flaws of Dual_EC_DRBG". A Few Thoughts on Cryptographic Engineering (англ.). 2013-09-18. Архивировано 20 августа 2016. Дата обращения: 15 декабря 2017.
  21. ↑ "A few more notes on NSA random number generators". A Few Thoughts on Cryptographic Engineering (англ.). 2013-12-28. Архивировано 24 июня 2018. Дата обращения: 15 декабря 2017.
  22. ↑ Six Cryptographers Whose Work on Dual EC DRBG Were Deemed Without Merit by RSA Chief Art Coviello. jeffreycarr.blogspot.ru. Дата обращения: 15 декабря 2017. Архивировано 15 декабря 2017 года.
  23. ↑ Ball, James (2013-09-06). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian (англ.). Архивировано 25 апреля 2018. Дата обращения: 15 декабря 2017.
  24. ↑ 1 2 "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. 2013-12-20. Архивировано 5 мая 2018. Дата обращения: 15 декабря 2017.
  25. ↑ "We don't enable backdoors in our crypto products, RSA tells customers". Ars Technica (англ.). Архивировано 12 августа 2018. Дата обращения: 15 декабря 2017.
  26. ↑ "Did NSA Put a Secret Backdoor in New Encryption Standard?". WIRED (англ.). Архивировано 23 ноября 2015. Дата обращения: 15 декабря 2017.
  27. ↑ Dual_EC_DRBG Added to Windows Vista - Schneier on Security. www.schneier.com. Дата обращения: 15 декабря 2017. Архивировано 10 июня 2018 года.
  28. ↑ CNG Algorithm Identifiers (Windows) (англ.). msdn.microsoft.com. Дата обращения: 15 декабря 2017. Архивировано 15 декабря 2017 года.
  29. ↑ SUPPLEMENTAL ITL BULLETIN FOR SEPTEMBER 2013. Дата обращения: 15 декабря 2017. Архивировано 26 мая 2018 года.
  30. ↑ Perlroth, Nicole. "Government Announces Steps to Restore Confidence on Encryption Standards". Bits Blog (англ.). Архивировано 25 марта 2018. Дата обращения: 15 декабря 2017.
  31. ↑ "Can You Trust NIST?". IEEE Spectrum: Technology, Engineering, and Science News (англ.). Архивировано 1 февраля 2016. Дата обращения: 15 декабря 2017.
  32. ↑ "Stop using NSA-influenced code in our products, RSA tells customers". Ars Technica (англ.). Архивировано 25 марта 2018. Дата обращения: 15 декабря 2017.
  33. ↑ "RSA warns developers not to use RSA products". A Few Thoughts on Cryptographic Engineering (англ.). 2013-09-20. Архивировано 24 апреля 2018. Дата обращения: 15 декабря 2017.
  34. ↑ "This page has been removed | News". The Guardian (англ.). Архивировано 13 февраля 2021. Дата обращения: 15 декабря 2017.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=Dual_EC_DRBG&oldid=132332153